package com.查找算法;


/**
 * 题目：统计一个数字在排序数组中出现的次数。
 * 示例：
 * 示例 1:
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: 2
 *
 * 示例 2:
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: 0

 * 思路：
 * 时间：
 * 日期：
 * 空间复杂度：
 * 时间复杂度：
 */
class Solution2 {

    /*
    法一：顺序查找，遍历数据，拿着这个目标数字，去数值中看出现了几次
    时间：O(n)
    空间：O(1)
     */
    public int search(int[] nums, int target) {
        int len=nums.length;
        int size=0;
        for (int i = 0; i < len; i++) {
            if (nums[i]==target)
                size++;
        }
        return size;
    }

    /*
    法二：二分查找，本题中数组是有序数组，可以用二分查找
     */
    public int search2(int[] nums, int target) {
        int len=nums.length;
        int i=0;
        int j=len-1;
        //查找右边界
        while(i<=j){
            int m=(i+j)/2;
            if(nums[m]<target) i=m+1;
            else if(nums[m]>target) j=m-1;
            else i=m+1;
        }
        int right=i;
        // 若数组中无 target ，则提前返回
        if(j >= 0 && nums[j] != target) return 0;
        //查找左边界
        i=0;j=len-1;
        while (i<=j){
            int m=(i+j)/2;
            if(nums[m]<target) i=m+1;
            else if(nums[m]>target) j=m-1;
            else j=m-1;
        }
        int left=j;
        return right-left-1;
    }

}
public class 剑指Offer53_I_在排序数组中查找数字I {
    public static void main(String[] args) {

    }
}
